Search

Your search keyword '"proof assistant"' showing total 2,829 results
Start Over Descriptor "proof assistant"

Refine your results

more »

more »

more »

more »
2,829 results on '"proof assistant"'

1. Engel’s Theorem in Mathlib.

Author

Nash, Oliver

Abstract

We discuss the theory of Lie algebras in Lean’s Mathlib library. Using nilpotency as the theme, we outline a computer formalisation of Engel’s theorem and an application to root space theory. We emphasise that all arguments work with coefficients in any commutative ring. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

2. A Parametrized Family of Tversky Metrics Connecting the Jaccard Distance to an Analogue of the Normalized Information Distance

Author

Kjos-Hanssen, Bjørn, Niraula, Saroj, Yoon, Soowhan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Artemov, Sergei, editor, and Nerode, Anil, editor

Published
2022
Full Text
View/download PDF

3. Accurate Calculation of Euclidean Norms Using Double-word Arithmetic.

Author

LEFÈVRE, VINCENT, LOUVET, NICOLAS, MULLER, JEAN-MICHEL, PICOT, JORIS, and RIDEAU, LAURENCE

Subjects
*FLOATING-point arithmetic, *ARITHMETIC, *SQUARE root
Abstract

We consider the computation of the Euclidean (or L2) norm of an n-dimensional vector in floating-point arithmetic. We review the classical solutions used to avoid spurious overflow or underflow and/or to obtain very accurate results. We modify a recently published algorithm (that uses double-word arithmetic) to allow for a very accurate solution, free of spurious overflows and underflows. To that purpose, we use a double-word square-root algorithm of which we provide a tight error analysis. The returned L2 norm will be within very slightly more than 0.5 ulp from the exact result, which means that we will almost always provide correct rounding. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

4. Formalising Szemerédi’s Regularity Lemma and Roth’s Theorem on Arithmetic Progressions in Isabelle/HOL.

Author

Edmonds, Chelsea, Koutsoukou-Argyraki, Angeliki, and Paulson, Lawrence C.

Abstract

We have formalised Szemerédi’s Regularity Lemma and Roth’s Theorem on Arithmetic Progressions, two major results in extremal graph theory and additive combinatorics, using the proof assistant Isabelle/HOL. For the latter formalisation, we used the former to first show the Triangle Counting Lemma and the Triangle Removal Lemma: themselves important technical results. Here, in addition to showcasing the main formalised statements and definitions, we focus on sensitive points in the proofs, describing how we overcame the difficulties that we encountered. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

5. Certification of an exact worst-case self-stabilization time.

Author

Altisen, Karine, Corbineau, Pierre, and Devismes, Stéphane

Subjects
*DISTRIBUTED algorithms, *CERTIFICATION
Abstract

Unlike qualitative properties such as correctness (safety and liveness), quantitative properties of distributed algorithms have only been certified in very few studies. This work is the first attempt to certify time complexity bounds of a fault-tolerant distributed algorithm. Our case study consists in formally proving, using the Coq proof assistant, the time complexity of the first Dijkstra's self-stabilizing token ring algorithm. In more detail, we formally prove both the self-stabilization and exact worst-case stabilization time of this algorithm assuming asynchronous settings. This latter result is obtained in two main steps. First, we certify a non-trivial upper bound on the stabilization time, i.e. , every execution in an N -size ring contains at most 3 ⋅ N ⋅ (N − 1) 2 − N − 1 steps if N ≥ 4 , at most 3 steps if N = 3 ; and in remaining cases, the stabilization time is zero. Then, for each case, we exhibit a possible execution whose complexity exactly matches those upper bounds. Notice that the tight bounds for N = 3 and N ≥ 4 were unknown until now, even among self-stabilization researchers. • This work is the first attempt to certify the time complexity of a fault-tolerant distributed algorithm. • The case study consists in the worst case stabilization time in steps of the first self-stabilizing algorithm proposed by Dijkstra. • The complexity analysis is complete: we certify the exact worst case stabilization time in steps of the algorithm. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

6. Discovering and certifying lower bounds for the online bin stretching problem.

Author

Böhm, Martin and Simon, Bertrand

Abstract

There are several problems in the theory of online computation where tight lower bounds on the competitive ratio are unknown and expected to be difficult to describe in a short form. A good example is the Online Bin Stretching problem, in which the task is to pack the incoming items online into bins while minimizing the load of the largest bin. Additionally, the optimal load of the entire instance is known in advance. The contribution of this paper is twofold. We use the Coq proof assistant to formalize the Online Bin Stretching problem and provide a program certifying lower bounds of this problem. Because of the size of the certificates, previously claimed lower bounds were never formally proven. To the best of our knowledge, this is the first use of a formal verification toolkit to certify a lower bound for an online problem. We also provide the first non-trivial lower bounds for Online Bin Stretching with 6, 7 and 8 bins, and increase the best known lower bound for 3 bins. We describe in detail the algorithmic improvements which were necessary for the discovery of the new lower bounds, which are several orders of magnitude more complex. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

7. Research on Automation Strategy of Coq

Author

Qian, Hanwei, Filipe, Joaquim, Editorial Board Member, Ghosh, Ashish, Editorial Board Member, Prates, Raquel Oliveira, Editorial Board Member, Zhou, Lizhu, Editorial Board Member, Sun, Xingming, editor, Zhang, Xiaorui, editor, Xia, Zhihua, editor, and Bertino, Elisa, editor

Published
2021
Full Text
View/download PDF

8. Automatic generation of proof terms in dependently typed programming languages

Author

Slama, Franck and Brady, Edwin

Subjects
005.13, Type theory, Equivalence, Equality, Proof automation, Correct-by-construction software, Type-driven development, Idris, Proof by reflection, Formal certification, Proof assistant, Algebraic structure, Ring, Group, Semi-ring, Monoid, Semi-group, Dependent types, Dependently typed programming languages, Proof obligation
Abstract

Dependent type theories are a kind of mathematical foundations investigated both for the formalisation of mathematics and for reasoning about programs. They are implemented as the kernel of many proof assistants and programming languages with proofs (Coq, Agda, Idris, Dedukti, Matita, etc). Dependent types allow to encode elegantly and constructively the universal and existential quantifications of higher-order logics and are therefore adapted for writing logical propositions and proofs. However, their usage is not limited to the area of pure logic. Indeed, some recent work has shown that they can also be powerful for driving the construction of programs. Using more precise types not only helps to gain confidence about the program built, but it can also help its construction, giving rise to a new style of programming called Type-Driven Development. However, one difficulty with reasoning and programming with dependent types is that proof obligations arise naturally once programs become even moderately sized. For example, implementing an adder for binary numbers indexed over their natural number equivalents naturally leads to proof obligations for equalities of expressions over natural numbers. The need for these equality proofs comes, in intensional type theories (like CIC and ML) from the fact that in a non-empty context, the propositional equality allows us to prove as equal (with the induction principles) terms that are not judgementally equal, which implies that the typechecker can't always obtain equality proofs by reduction. As far as possible, we would like to solve such proof obligations automatically, and we absolutely need it if we want dependent types to be use more broadly, and perhaps one day to become the standard in functional programming. In this thesis, we show one way to automate these proofs by reflection in the dependently typed programming language Idris. However, the method that we follow is independent from the language being used, and this work could be reproduced in any dependently-typed language. We present an original type-safe reflection mechanism, where reflected terms are indexed by the original Idris expression that they represent, and show how it allows us to easily construct and manipulate proofs. We build a hierarchy of correct-by-construction tactics for proving equivalences in semi-groups, monoids, commutative monoids, groups, commutative groups, semi-rings and rings. We also show how each tactic reuses those from simpler structures, thus avoiding duplication of code and proofs. Finally, and as a conclusion, we discuss the trust we can have in such machine-checked proofs.

Published
2018

9. Envelopes and waves: safe multivehicle collision avoidance for horizontal non-deterministic turns.

Author

Kouskoulas, Yanni, Machado, T. J., Genin, Daniel, Schmidt, Aurora, Papusha, Ivan, and Brulé, Joshua

Subjects
*KINEMATICS, *POSSIBILITY, *SPEED, *LIBRARIES
Abstract

We present an approach to analyze the safety of asynchronous, independent, non-deterministic, turn-to-bearing horizontal maneuvers for two vehicles. Future turn rates, final bearings, and continuously varying ground speeds throughout the encounter are unknown but restricted to known ranges. We develop a library of formal proofs about turning kinematics and apply the library to create a formally verified timing computation. Additionally, we create a technique that evaluates future collision possibilities that is based on waves of position possibilities and relies on the timing computation. The result either determines that the encounter will be collision-free, or computes a safe overapproximation for when and where collisions may occur. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

10. A Bi-Directional Extensible Interface Between Lean and Mathematica.

Author

Lewis, Robert Y. and Wu, Minchao

Subjects
COMPUTER systems, INFORMATION sharing, SYNTAX (Grammar), DATABASES, NOTEBOOKS
Abstract

We implement a user-extensible ad hoc connection between the Lean proof assistant and the computer algebra system Mathematica. By reflecting the syntax of each system in the other and providing a flexible interface for extending translation, our connection allows for the exchange of arbitrary information between the two systems. We show how to make use of the Lean metaprogramming framework to verify certain Mathematica computations, so that the rigor of the proof assistant is not compromised. We also use Mathematica as an untrusted oracle to guide proof search in the proof assistant and interact with a Mathematica notebook from within a Lean session. In the other direction, we import and process Lean declarations from within Mathematica. The proof assistant library serves as a database of mathematical knowledge that the CAS can display and explore. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

11. On Trust in Mathematics: Some Case Studies

Author

Bellotti, Luca, Moriconi, Enrico, Magnani, Lorenzo, Editor-in-Chief, Aliseda, Atocha, Editorial Board Member, Longo, Giuseppe, Editorial Board Member, Sinha, Chris, Editorial Board Member, Thagard, Paul, Editorial Board Member, Woods, John, Editorial Board Member, and Fabris, Adriano, editor

Published
2020
Full Text
View/download PDF

12. Formally Verifying Proofs for Algebraic Identities of Matrices

Author

Schmitz, Leonard, Levandovskyy, Viktor, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Benzmüller, Christoph, editor, and Miller, Bruce, editor

Published
2020
Full Text
View/download PDF

13. Equality Checking for General Type Theories in Andromeda 2

Author

Bauer, Andrej, Haselwarter, Philipp G., Petković, Anja, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bigatti, Anna Maria, editor, Carette, Jacques, editor, Davenport, James H., editor, Joswig, Michael, editor, and de Wolff, Timo, editor

Published
2020
Full Text
View/download PDF

14. Formalization of Double-Word Arithmetic, and Comments on "Tight and Rigorous Error Bounds for Basic Building Blocks of Double-Word Arithmetic".

Author

MULLER, JEAN-MICHEL and RIDEAU, LAURENCE

Subjects
*COMPUTER arithmetic, *FLOATING-point arithmetic
Abstract

Recently, a complete set of algorithms for manipulating double-word numbers (some classical, some new) was analyzed [16]. We have formally proven all the theorems given in that article, using the Coq proof assistant. The formal proof work led us to: (i) locate mistakes in some of the original paper proofs (mistakes that, however, do not hinder the validity of the algorithms), (ii) significantly improve some error bounds, and (iii) generalize some results by showing that they are still valid if we slightly change the rounding mode. The consequence is that the algorithms presented in [16] can be used with high confidence, and that some of them are even more accurate than what was believed before. This illustrates what formal proof can bring to computer arithmetic: beyond mere (yet extremely useful) verification, correction, and consolidation of already known results, it can help to find new properties. All our formal proofs are freely available. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

15. AN EXTENSIBLE EQUALITY CHECKING ALGORITHM FOR DEPENDENT TYPE THEORIES.

Author

BAUER, ANDREJ and KOMEL, ANJA PETKOVIC

Subjects
ALGORITHMS, ARGUMENT
Abstract

We present a general and user-extensible equality checking algorithm that is applicable to a large class of type theories. The algorithm has a type-directed phase for applying extensionality rules and a normalization phase based on computation rules, where both kinds of rules are defined using the type-theoretic concept of object-invertible rules. We also give sufficient syntactic criteria for recognizing such rules, as well as a simple pattern-matching algorithm for applying them. A third component of the algorithm is a suitable notion of principal arguments, which determines a notion of normal form. By varying these, we obtain known notions, such as weak head-normal and strong normal forms. We prove that our algorithm is sound. We implemented it in the Andromeda 2 proof assistant, which supports user-definable type theories. The user need only provide the equality rules they wish to use, which the algorithm automatically classifies as computation or extensionality rules, and select appropriate principal arguments. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

16. Distilling the Requirements of Gödel's Incompleteness Theorems with a Proof Assistant.

Author

Popescu, Andrei and Traytel, Dmitriy

Subjects
GODEL'S theorem, MECHANIZATION, MATHEMATICAL logic, FIRST-order logic, NUMERALS
Abstract

We present an abstract development of Gödel's incompleteness theorems, performed with the help of the Isabelle/HOL proof assistant. We analyze sufficient conditions for the applicability of our theorems to a partially specified logic. In addition to the usual benefits of generality, our abstract perspective enables a comparison between alternative approaches from the literature. These include Rosser's variation of the first theorem, Jeroslow's variation of the second theorem, and the Świerczkowski–Paulson semantics-based approach. As part of the validation of our framework, we upgrade Paulson's Isabelle proof to produce a mechanization of the second theorem that does not assume soundness in the standard model, and in fact does not rely on any notion of model or semantic interpretation. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

17. On Formalization of Semantics of Real-Time and Cyber-Physical Systems

Author

Ivanov, Ievgen, Panchenko, Taras, Nikitchenko, Mykola, Sunmade, Fabunmi, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Hu, Zhengbing, editor, Petoukhov, Sergey, editor, Dychka, Ivan, editor, and He, Matthew, editor

Published
2019
Full Text
View/download PDF

18. Verification by Construction of Distributed Algorithms

Author

Méry, Dominique, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Hierons, Robert Mark, editor, and Mosbah, Mohamed, editor

Published
2019
Full Text
View/download PDF

19. A Mechanized Theory of Program Refinement

Author

Sall, Boubacar Demba, Peschanski, Frédéric, Chailloux, Emmanuel, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Ait-Ameur, Yamine, editor, and Qin, Shengchao, editor

Published
2019
Full Text
View/download PDF

20. A Formally Verified Monitor for Metric First-Order Temporal Logic

Author

Schneider, Joshua, Basin, David, Krstić, Srđan, Traytel, Dmitriy, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Finkbeiner, Bernd, editor, and Mariani, Leonardo, editor

Published
2019
Full Text
View/download PDF

21. Continuous vs. Discrete Asynchronous Moves: A Certified Approach for Mobile Robots

Author

Balabonski, Thibaut, Courtieu, Pierre, Pelle, Robin, Rieg, Lionel, Tixeuil, Sébastien, Urbain, Xavier, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Atig, Mohamed Faouzi, editor, and Schwarzmann, Alexander A., editor

Published
2019
Full Text
View/download PDF

22. Integrating Formal Schedulability Analysis into a Verified OS Kernel

Author

Guo, Xiaojie, Lesourd, Maxime, Liu, Mengqi, Rieg, Lionel, Shao, Zhong, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Dillig, Isil, editor, and Tasiran, Serdar, editor

Published
2019
Full Text
View/download PDF

23. Methods of Formal Software Verification in the Context of Distributed Systems

Author

Fatkina, Anna, Iakushkin, Oleg, Selivanov, Dmitry, Korkhov, Vladimir, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Misra, Sanjay, editor, Gervasi, Osvaldo, editor, Murgante, Beniamino, editor, Stankova, Elena, editor, Korkhov, Vladimir, editor, Torre, Carmelo, editor, Rocha, Ana Maria A.C., editor, Taniar, David, editor, Apduhan, Bernady O., editor, and Tarantino, Eufemia, editor

Published
2019
Full Text
View/download PDF

24. Formal Methods for Mobile Robots

Author

Potop-Butucaru, Maria, Sznajder, Nathalie, Tixeuil, Sébastien, Urbain, Xavier, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Flocchini, Paola, editor, Prencipe, Giuseppe, editor, and Santoro, Nicola, editor

Published
2019
Full Text
View/download PDF

25. Extended Floyd-Hoare Logic over Relational Nominative Data

Author

Nikitchenko, Mykola, Ivanov, Ievgen, Korniłowicz, Artur, Kryvolap, Andrii, Barbosa, Simone Diniz Junqueira, Series editor, Chen, Phoebe, Series editor, Filipe, Joaquim, Series editor, Kotenko, Igor, Series editor, Sivalingam, Krishna M., Series editor, Washio, Takashi, Series editor, Yuan, Junsong, Series editor, Zhou, Lizhu, Series editor, Bassiliades, Nick, editor, Ermolayev, Vadim, editor, Fill, Hans-Georg, editor, Yakovyna, Vitaliy, editor, Mayr, Heinrich C., editor, Nikitchenko, Mykola, editor, Zholtkevych, Grygoriy, editor, and Spivakovsky, Aleksander, editor

Published
2018
Full Text
View/download PDF

26. Formalization of the Nominative Algorithmic Algebra in Mizar

Author

Korniłowicz, Artur, Kryvolap, Andrii, Nikitchenko, Mykola, Ivanov, Ievgen, Kacprzyk, Janusz, Series editor, Pal, Nikhil R., Advisory editor, Bello Perez, Rafael, Advisory editor, Corchado, Emilio S., Advisory editor, Hagras, Hani, Advisory editor, Kóczy, László T., Advisory editor, Kreinovich, Vladik, Advisory editor, Lin, Chin-Teng, Advisory editor, Lu, Jie, Advisory editor, Melin, Patricia, Advisory editor, Nedjah, Nadia, Advisory editor, Nguyen, Ngoc Thanh, Advisory editor, Wang, Jun, Advisory editor, Świątek, Jerzy, editor, Borzemski, Leszek, editor, and Wilimowska, Zofia, editor

Published
2018
Full Text
View/download PDF

27. HOL Light QE

Author

Carette, Jacques, Farmer, William M., Laskowski, Patrick, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Avigad, Jeremy, editor, and Mahboubi, Assia, editor

Published
2018
Full Text
View/download PDF

28. Formal Verification of the Correspondence Between Call-by-Need and Call-by-Name

Author

Mizuno, Masayuki, Sumii, Eijiro, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Gallagher, John P., editor, and Sulzmann, Martin, editor

Published
2018
Full Text
View/download PDF

29. A Formalized Procedure for Database Horizontal Fragmentation in Isabelle/HOL Proof Assistant

Author

Salmi, Cheikh, Chaabani, Mohamed, Mezghiche, Mohamed, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Abdelwahed, El Hassan, editor, Bellatreche, Ladjel, editor, Golfarelli, Mattéo, editor, Méry, Dominique, editor, and Ordonez, Carlos, editor

Published
2018
Full Text
View/download PDF

30. Kuratowski finite sets in the UniMath Library

Abstract

This paper focuses on implementing and verifying the proofs presented in ``Finite Sets in Homotopy Type Theory" within the UniMath library. The UniMath library currently lacks support for higher inductive types, which are crucial for reasoning about finite sets in Homotopy Type Theory. This paper addresses that issue and introduces higher inductive types to UniMath. This is used to develop a computer-checked implementation of the proofs within "Finite Sets in Homotopy Type Theory." This implementation enables future research on finite sets in HoTT by providing accessible and reliable proofs. This paper defines finite sets as Kuratowski-finite. This is in contrast with the most common notion of finiteness, e.g. Bishop-finite and enumerated types. I argue that Kuratowski-finiteness is the most general finite for which the usual operations of finite types and sub-objects can be operated upon., CSE3000 Research Project, Computer Science and Engineering

Published
2023

31. A Computer-Checked Library of Category Theory: Functors and F-Coalgebras

Abstract

This research project aims to develop a computer-checked library of category theory within the Lean proof assistant, with a specific emphasis on concepts and examples relevant to functional programming. Category theory offers a robust mathematical framework that allows for the abstraction and comprehension of concepts across diverse fields, including computer science. Additionally, the project will explore the application of final coalgebras, particularly in the context of understanding infinite data structures. By creating a formalized category theory library within Lean, our objective is to enhance our understanding of functional programming and programming language concepts. Moreover, we aim to facilitate the study of these topics by providing a comprehensible library and a rigorous foundation for program reasoning, thereby benefiting researchers and practitioners in the field., CSE3000 Research Project, Computer Science and Engineering

Published
2023

32. A computer-checked library of category theory: Formally verifying currying via the product-exponential adjunction

Abstract

Existing implementations of category theory for proof assistants aim to be as generic as possible in order to be reusable and extensible, often at the expense of readability and clarity. We present a (partial) formalisation of category theory in the proof assistant Lean limited in purpose to explaining currying, intended to be faithful to the language and definitions used in mathematics literature. We also present some design features of our library and contrast the extent and educational merit with other implementations., CSE3000 Research Project, Computer Science and Engineering

Published
2023

33. The monad and examples from Haskell: A computer-checked library for Category Theory in Lean

Abstract

Category Theory is a widely used field of Mathematics. Some concepts from it are often used in functional programming. This paper will focus on the Monad and a few implementations of it from Haskell. We will also present the computer-checked library we have written to help us in this task., https://github.com/sgciprian/ct, CSE3000 Research Project, Computer Science and Engineering

Published
2023

34. A computer-checked library of category theory: Defining functors and their algebras

Abstract

Category theory is a branch of abstract mathematics that aims to give a high-level overview of relations between objects. Proof assistants are tools that aid in verifying the correctness of mathematical proofs. To reason about category theory using such assistants, fundamental notions have to be defined. Computer-checked libraries contain all relevant structures and theorems in an accessible way for end users. However, current libraries of category theory are not welcoming to people without in-depth domain knowledge. This paper introduces a library of category theory tailored towards newcomers to the field as well as the learning journey of the authors. We describe the project’s structure, design choices and provide examples of the main features. Moreover, a detailed overview is provided of F-algebras and their relation with inductive data types found in functional programming languages. Construction and evaluation of types like lists and binary trees can be defined in terms of algebras. They provide a general framework for recursion over these types which allow us to reason about them with simple functions., CSE3000 Research Project, Computer Science and Engineering

Published
2023

35. Formalising Mathematics – in Praxis; A Mathematician's First Experiences with Isabelle/HOL and the Why and How of Getting Started.

Author

Koutsoukou-Argyraki, Angeliki

Abstract

This is an account of a mathematician's first experiences with the proof assistant (interactive theorem prover) Isabelle/HOL, including a discussion on the rationale behind formalising mathematics and the choice of Isabelle/HOL in particular, some instructions for new users, some technical and conceptual observations focussing on some of the first difficulties encountered, and some thoughts on the use and potential of proof assistants for mathematics. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

36. Automated Reasoning with Analytic Tableaux and Related Methods

Author

Ramanayake, Revantha and Urban, Josef

Subjects
tableaux, tableaux calculus, sequent calculus, proof theory, theorem proving, proof assistant, natural deduction, formalized proof, decision procedures, automated deduction, SMT, resolution, cut-elimination, non-classical logics, modal logic, intuitionistic, inear logic, substructural logic, separation logic, bic Book Industry Communication::U Computing & information technology::UY Computer science::UYQ Artificial intelligence, bic Book Industry Communication::U Computing & information technology::UY Computer science::UYA Mathematical theory of computation, bic Book Industry Communication::U Computing & information technology::UM Computer programming / software development, bic Book Industry Communication::U Computing & information technology::UM Computer programming / software development::UMZ Software Engineering, bic Book Industry Communication::U Computing & information technology::UY Computer science::UYD Systems analysis & design, bic Book Industry Communication::U Computing & information technology::UM Computer programming / software development::UMB Algorithms & data structures
Abstract

This open access book constitutes the proceedings of the proceedings of the 32nd International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2023, held in Prague, Czech Republic, during September 18-21, 2023. The 20 full papers and 5 short papers included in this book together with 5 abstracts of invited talks were carefully reviewed and selected from 43 submissions. They present research on all aspects of the mechanization of reasoning with tableaux and related methods. The papers are organized in the following topical sections: tableau calculi; sequent calculi; theorem proving; non-wellfounded proofs; modal logics; linear logic and MV-algebras; separation logic; and first-order logics.

Published
2023
Full Text
View/download PDF

37. Derivations and Formalizations

Author

Ayala-Rincón, Mauricio, de Moura, Flávio L. C., Mackie, Ian, Series editor, Abramsky, Samson, Advisory board, Breitman, Karin, Advisory board, Hankin, Chris, Advisory board, Kozen, Dexter C., Advisory board, Pitts, Andrew, Advisory board, Riis Nielson, Hanne, Advisory board, Skiena, Steven S, Advisory board, Stewart, Iain, Advisory board, Ayala-Rincón, Mauricio, and de Moura, Flávio L. C.

Published
2017
Full Text
View/download PDF

39. Friends with Benefits : Implementing Corecursion in Foundational Proof Assistants

Author

Blanchette, Jasmin Christian, Bouzy, Aymeric, Lochbihler, Andreas, Popescu, Andrei, Traytel, Dmitriy, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Yang, Hongseok, editor

Published
2017
Full Text
View/download PDF

40. Implementing Open Call-by-Value

Author

Accattoli, Beniamino, Guerrieri, Giulio, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dastani, Mehdi, editor, and Sirjani, Marjan, editor

Published
2017
Full Text
View/download PDF

41. Certified Password Quality : A Case Study Using Coq and Linux Pluggable Authentication Modules

Author

Ferreira, João F., Johnson, Saul A., Mendes, Alexandra, Brooke, Phillip J., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Polikarpova, Nadia, editor, and Schneider, Steve, editor

Published
2017
Full Text
View/download PDF

42. Auto-Active Proof of Red-Black Trees in SPARK

Author

Dross, Claire, Moy, Yannick, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Barrett, Clark, editor, Davies, Misty, editor, and Kahsai, Temesghen, editor

Published
2017
Full Text
View/download PDF

43. Computing a Correct and Tight Rounding Error Bound Using Rounding-to-Nearest

Author

Boldo, Sylvie, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bogomolov, Sergiy, editor, Martel, Matthieu, editor, and Prabhakar, Pavithra, editor

Published
2017
Full Text
View/download PDF

44. Eliminating Irrelevant Non-determinism in Functional Logic Programs

Author

Antoy, Sergio, Hanus, Michael, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Lierler, Yuliya, editor, and Taha, Walid, editor

Published
2017
Full Text
View/download PDF

45. Graphs as Transitive Sets

Author

Omodeo, Eugenio G., Policriti, Alberto, Tomescu, Alexandru I., Omodeo, Eugenio G., Policriti, Alberto, and Tomescu, Alexandru I.

Published
2017
Full Text
View/download PDF

46. The HHL Prover

Author

Zhan, Naijun, Wang, Shuling, Zhao, Hengjun, Zhan, Naijun, Wang, Shuling, and Zhao, Hengjun

Published
2017
Full Text
View/download PDF

47. Proof assistants for undergraduate mathematics education: elements of an a priori analysis

Author

Bartzia, Evmorfia-Iro, Beffara, Emmanuel, Meyer, Antoine, Narboux, Julien, Laboratoire Alexander Grothendieck (LAG), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Modèles et Technologies pour l’Apprentissage Humain (MeTAH ), Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Institut de Recherche sur l’Enseignement des Mathématiques [Grenoble] (IREM), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, IREM de Paris, Université Paris Cité (UPCité), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche sur l'Enseigment des Mathématiques [Strasbourg] (IREM), Université de Strasbourg - UFR Mathématique et Informatique (UNISTRA UFR MI), and Université de Strasbourg (UNISTRA)-Université de Strasbourg (UNISTRA)

Subjects
logic, Didactics of University Mathematics, teaching proof, computer assisted theorem proving, proof, proof assistant, reasoning, [INFO.EIAH]Computer Science [cs]/Technology for Human Learning, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract

This paper presents an a priori analysis of the use of six different interactive proof assistants for education, based on the resolution of a typical undergraduate exercise on abstract functions. It proposes to analyze these tools according to three main categories of aspects: language and interaction mode, automation and user assistance, and proof structure and visualization. We argue that this analysis may help formulate and clarify further research questions on the possible impact of such tools on the development of reasoning and proving skills.

Published
2023

48. Implementacija in uporaba dokazovalnega pomočnika

Author

ZUPANČIČ, BLAŽ and Bauer, Andrej

Subjects
dokazovalni pomočnik, type theory, proof assistant, teorija tipov
Abstract

Dokazovalni pomočnik je računalniški program za izdelavo formalnih matematičnih dokazov. To diplomsko delo obravnava izdelavo in uporabo preprostega tovrstnega programa. Za osnovo dokazovalnega pomočnika smo vzeli implementacijo minimalistične teorije tipov, ki jo je v programskem jeziku OCaml razvil prof. dr. Andrej Bauer. Njegovo implementacijo smo razširili s tipom naravnih števil in tipi identifikacij, da smo lahko v njej izrazili in dokazali osnovne lastnosti seštevanja. A proof assistant is a software tool for development of formal proofs. This thesis demonstrates implementation and use of one such tool. As the basis of our proof assistant we used an implementation of a minimalist type theory developed by prof. dr. Andrej Bauer using the OCaml programming language. We expanded his implementation with the type of natural numbers and identity types which allowed us to express and prove the basic properties of addition.

Published
2023

49. A Highly-Available Move Operation for Replicated Trees

Author

Kleppmann, M, Mulligan, DP, Gomes, VBF, Beresford, AR, Kleppmann, M [0000-0001-7252-6958], Mulligan, DP [0000-0003-4643-3541], Gomes, VBF [0000-0002-2954-4648], Beresford, AR [0000-0003-0818-6535], and Apollo - University of Cambridge Repository

Subjects
Correctness, Conflict-free replicated data types (CRDTs), distributed filesystems, Computer science, Distributed computing, HOL, Drives, Synchronization, formal verification, Block (data storage), computer.programming_language, Internet, Proof assistant, Data models, XML, JSON, distributed collaboration, Tree (data structure), Tree structure, Computational Theory and Mathematics, Software bug, Computer bugs, Hardware and Architecture, Signal Processing, computer, Software
Abstract

Replicated tree data structures are a fundamental building block of distributed filesystems, such as Google Drive and Dropbox, and collaborative applications with a JSON or XML data model. These systems need to support a move operation that allows a subtree to be moved to a new location within the tree. However, such a move operation is difficult to implement correctly if different replicas can concurrently perform arbitrary move operations, and we demonstrate bugs in Google Drive and Dropbox that arise with concurrent moves. In this article we present a CRDT algorithm that handles arbitrary concurrent modifications on trees, while ensuring that the tree structure remains valid (in particular, no cycles are introduced), and guaranteeing that all replicas converge towards the same consistent state. Our algorithm requires no synchronous coordination between replicas, making it highly available in the face of network partitions. We formally prove the correctness of our algorithm using the Isabelle/HOL proof assistant, and evaluate the performance of our formally verified implementation in a geo-replicated setting.

Published
2022

50. Implementation of the Composition-nominative Approach to Program Formalization in Mizar

Author

Ievgen Ivanov, Artur Kornilowicz, and Mykola Nikitchenko

Subjects
Formal methods, program semantics, semistructured data, formalization, proof assistant, Electronic computers. Computer science, QA75.5-76.95
Abstract

In this paper we describe an ongoing work on implementation of the composition-nominative approach to program formalization in Mizar proof assistant based on the first-order logic and axiomatic set theory. The further aim of this work is development of a formal verification tool for software which processes and communicates with complex forms of data.

Published
2018

Catalog

Books, media, physical & digital resources
See catalog results